package Interview.Amazon;

import domain.ListNode;
import util.ListNodeUtil;

/**
 * 3 -> 1 -> 6 -> 8 -> 5 -> 2 -> 9 -> 4 -> 7
 * p1位于1，比头结点3小，p2前进一步，与p1交换
 * 3 -> 1 -> 6 -> 8 -> 5 -> 2 -> 9 -> 4 -> 7
 * p1位于2，比3小，p2前进一步到6的位置，与p1(2)交换
 * 3 -> 1 -> 2 -> 8 -> 5 -> 6 -> 9 -> 4 -> 7
 * p2遍历结束，p2停留在2的位置，与头结点交换,partition位于3的位置
 * 2 -> 1 -> 3 -> 8 -> 5 -> 6 -> 9 -> 4 -> 7
 * @Auther: leiwenkang
 * @Date: 2020/7/30 15:09
 * @Description:
 */
public class Test05链表的快速排序 {
    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        ListNode p1 = new ListNode(1);
        ListNode p2 = new ListNode(6);
        ListNode p3 = new ListNode(8);
        ListNode p4 = new ListNode(5);
        ListNode p5 = new ListNode(2);
        ListNode p6 = new ListNode(9);
        ListNode p7 = new ListNode(4);
        ListNode p8 = new ListNode(7);

        head.next = p1;
        p1.next = p2;
        p2.next = p3;
        p3.next = p4;
        p4.next = p5;
        p5.next = p6;
        p6.next = p7;
        p7.next = p8;

        ListNode res = new Test05链表的快速排序().quickSort(head);

        ListNodeUtil.printListNode(res);
    }

    //快排
    public ListNode quickSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        quickSort(head, null);
        return head;
    }

    private void quickSort(ListNode head, ListNode tail) {
        if (head == tail) {
            return;
        }

        ListNode p1 = head;
        ListNode p2 = head;

        while (p2 != tail){
            if(p2.val < head.val){
                p1 = p1.next;

                int temp = p1.val;
                p1.val = p2.val;
                p2.val = temp;
            }
            p2 = p2.next;
        }

        //p1与基准交换
        if(p1 != head){
            int temp = p1.val;
            p1.val = head.val;
            head.val = temp;
        }

        quickSort(head,p1);
        quickSort(p1.next, tail);
    }

}